package com.二叉树.练习题;

import java.util.Arrays;

public class Leetcode106 {
    /**
     * 根据中序与后序遍历结果构造二叉树
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
     * postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
     * 输出：[3,9,20,null,null,15,7]
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0){
            return null;
        }
        int rootVal = postorder[postorder.length-1];
        TreeNode root = new TreeNode(rootVal);
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i] == rootVal){
                int[] inLeft = Arrays.copyOfRange(inorder,0,i);
                int[] inRight = Arrays.copyOfRange(inorder,i+1,inorder.length);
                int[] preLeft = Arrays.copyOfRange(postorder,0,i);
                int[] preRight = Arrays.copyOfRange(postorder,i,postorder.length-1);
                root.left = buildTree(inLeft,preLeft);
                root.right = buildTree(inRight,preRight);
                break;
            }
        }
        return root;
    }
}
